As is known in the art, large mainframe computer systems such as host computers or servers require large capacity data storage systems. One type of data storage system is a magnetic disk storage system. Here, a bank of disk drives and host computer/server are coupled together through an interface. The interface includes CPU, or “front end”, controllers (or directors) and “back end” disk controllers (or directors). The interface operates the controllers (or directors) in such a way that they are transparent to the host computer/server. That is, data is stored in, and retrieved from, the bank of disk drives in such a way that the host computer/server merely thinks it is operating with one mainframe memory. One such system is described in U.S. Pat. No. 5,206,939, entitled “System and Method for Disk Mapping and Data Retrieval”, inventors Moshe Yanai, Natan Vishlitzky, Bruno Alterescu and Daniel Castel, issued Apr. 27, 1993, and assigned to the same assignee as the present invention.
As described in such U.S. Patent, the interface may also include, in addition to the CPU controllers (or directors) and disk controllers (or directors), addressable cache memories, i.e., cache. The cache memory is a semiconductor memory and is provided to rapidly store data from the main frame computer system before storage in the disk drives, and, on the other hand, store data from the disk drives prior to being sent to the main frame computer. The cache memory being a semiconductor memory, as distinguished from a magnetic memory as in the case of the disk drives, is much faster than the disk drives in reading and writing data. Another type of interface is described in U.S. Pat. No. 6,651,130 issued Nov. 18, 2003, entitled data Storage System Having Separate Data Transfer Section and Message Network With Bus Arbitration, inventor Thibault, assigned to the same assignee as the present invention, the entire subject matter thereof being incorporated herein by reference. As described therein during a read operation, when data is requested by the host computer/server, the system interface first queries the cache memory to determined whether the data is in cache, i.e., a read “hit”. If in cache, the data is sent from cache to the host computer/server. On the other hand, if the requested data is not in cache, i.e., a read “miss”, the interface reads the data from the disk drives and then stores the data read from the disk drives into cache. The interface then reads the data from cache and sends it to the host computer/server.
As is also known in the art, it is desirable to predict host computer/server reads and thereby read data into cache before the host computer/server requests it to thereby improve latency and throughput. One technique used is a disk drive data prefetch. Here, caches use prefetch predictions based on recent history. Prefetch predictions use recent history to attempt to predict how much data to read from the disk drive and then load into cache. They are attempting to predict the length (i.e., number of successive pages of the disk drive) to read. For disk arrays, a logically sequential run is typically also physically sequential (or striped sequentially across multiple disks). When a read is requested from an area of the disk that is not in the cache, the prefetch algorithm starts to collect data to determine how much to read from the disk using the current state of the cache itself. As more reads request to that area are issued, more data is collected into the cache. Because they use only short-term history, prefetch algorithms will typically under-predict the length of a sequential run at the beginning and over-predict the length at the end. The initial under-prediction incurs extra latency, and the over-prediction at the end wastes disk time and cache space.
One example of a short-term prefetch algorithm is shown in FIG. 1. In this example, the disk drive stores data A through M. The disk drive has successive storage slots or pages, 1 through 26 as shown in FIG. 2A. Data A through F are stored on successive disk drive pages 1 through 6, respectively, as shown in FIG. 2A. Data G is stored in page 21, data H in page 24, data I in page 23, data J in page 22, data K in page 25, data L in page 26 and data M in page 20, as shown.
Referring now also to FIG. 1, the host computer/server will sequentially request data A through M. When the host computer/server requests data A, the algorithm shown in FIG. 1 results in data A (which is in page 1) being read from disk and stored in cache and then sent to the host computer/server. It is first assumed that the cache is empty.
When the host computer/server requests data B, the algorithm causes data B (which is in page 2) to be stored in cache and then transferred to the host computer/server. It is first noted that, storage on the disk drives 141 is organized into pages, where each page contains a fixed amount of data (e.g., 4096 bytes). Each page on a disk drive has a page numerical designation, i.e., page number, which uniquely physically identifies the page on the drive. A read from a disk drive 141 must specify the first page to read from and the number of pages to read. For a given page or requested, the previous page to the given, or requested page, is the page which has a page number exactly one less than the given page. Similarly, the next page is the page that has a page number exactly one greater. Thus, as used herein, the term “previous” page to a requested page means physically preceding the requested page. More particularly, the pages are positioned successively on the disk drive. The term “previous” page means the page positioned physically on the disk drive in a position preceding the position on the disk drive of the requested page. Further, in the example in FIG. 2A, the data is read sequentially in time alphabetically; thus, the time sequence of the requested data is A, B, C, D, E, F, G, H, I, J, K, L, M, etc.
The algorithm also notes that page 2 follows page 1 (i.e., page 1 is the page previous to page 2) which was read from disk and thus the next page, i.e., page 3, is read from disk and stored in cache; i.e., the data in page 3 is prefetched. It is noted that page 3 has data C. Thus, data C was prefetched when data B was requested.
When the host computer/server requests data C the algorithm notes that data C was prefetched and is already in cache, i.e., a “hit”.
When the host computer/server requests data D, the algorithm causes data D (which is in page 4) to be stored in cache and then transferred to the host computer/server. The algorithm also notes that page 4 follows page 3 (i.e., the previous page) which was read from disk and thus the next page, i.e., page 5, is read from disk and stored in cache; i.e., the data in page 5 is prefetched. It is noted that page 5 has data E. Thus, data E was prefetched when data D was requested.
When the host computer/server requests data E the algorithm notes that data E was pre-fetched and is already in cache, i.e., a “hit”.
When the host computer/server requests data F, the algorithm causes data F (which is in page 6) to be stored in cache and then transferred to the host computer/server. The algorithm also notes that page 6 follows page 5 (i.e., the previous page) which was read from disk and thus the next page, i.e., page 7, is read from disk and stored in cache; i.e., the data in page 7 is prefetched. Note that page 7 is never requested by the host computer/server in this example.
When the host computer/server requests data G, the algorithm causes data G (which is in page 21 to be stored in cache and then transferred to the host computer/server. The algorithm also notes that the previous page 20 has not been requested so there is no prefetch.
When the host computer/server requests data H, the algorithm causes data H (which is in page 24 to be stored in cache and then transferred to the host computer/server. The algorithm also notes that previous page 23 has not been requested so there is no prefetch.
When the host computer/server requests data I, the algorithm causes data I (which is in page 23 to be stored in cache and then transferred to the host computer/server. The algorithm also notes that previous page 22 has not been requested so there is no prefetch.
When the host computer/server requests data J, the algorithm causes data J (which is in page 22 to be stored in cache and then transferred to the host computer/server. The algorithm also notes that previous page 21 has been requested, so prefetch is considered, but page 23 is already in cache, so there is no prefetch.
When the host computer/server requests data K, the algorithm causes data K (which is in page 25 to be stored in cache and then transferred to the host computer/server. The algorithm also notes that previous page 24 has been requested so there is a prefetch of the data on next page 26, i.e., data L. Thus, data L was prefetched when data K was requested.
When the host computer/server requests data L the algorithm notes that data L was prefetched and is already in cache, i.e., a “hit”.
When the host computer/server requests data M, the algorithm causes data M (which is in page 20) to be stored in cache and then transferred to the host computer/server. The algorithm also notes that previous page 19 has not been requested so there is no prefetch. While the algorithm shown in FIG. 1 reduces the number of read requests from 13 to 10, in this example, it would be desirable to reduce the number of read requests further, while avoiding reading pages that will not be referenced by the host computer/server.